package com.ly.algorithm.offerpointer;

/**
 * @Classname Offer42
 * @Description
 *
 * 输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出: 6
 * 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
 *
 * @Date 2021/1/31 15:09
 * @Author 冷心影翼
 */
public class Offer42 {

    public static void main(String[] args) {
        Solution42 solution42 = new Solution42();
        System.out.println(solution42.maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
    }

}


class Solution42 {
    public int maxSubArray(int[] nums) {
        if(nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int max = dp[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
            max = Math.max(dp[i],max);
        }
        return max;
    }
}